<?php 
/**
 * 二叉搜索树与双向链表
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
 */

class TreeNode{
    public $val;
    public $left = null;
    public $right = null;
    public function __construct($val){
        $this->val = $val;
    }
}


/** 
 * 非递归
 *
 */
function ConvertBSTToBiList($treeNode)
{
	if ($treeNode == null) {
		return null;
	}
	if ($treeNode->left == null && ($treeNode->right == null)) {
		return $treeNode;
	}
    $stack = [];
	$curNode = $treeNode;
	$pre = null;
    $isFirst = true;
	while ($curNode!=null || (!empty($stack))) {
		// 左节点的根节点入栈
		while ($curNode != null) {
			array_push($stack, $curNode);
			$curNode = $curNode->left;
		}
        // 出栈
	    $curNode = array_pop($stack);
		if ($isFirst) { // 将第一个出栈的，变更为头
			$treeNode = $curNode;
			$pre = $treeNode;
			$isFirst = false;
		} else {
			$pre->right = $curNode;
			$curNode->left = $pre;
			$pre = $curNode;
		}

		$curNode = $curNode->right;
	}
	return $treeNode;
}


/** 
 * 中序递归

1.将左子树构造成双链表，并返回链表头节点。
2.定位至左子树双链表最后一个节点。
3.如果左子树链表不为空的话，将当前root追加到左子树链表。
4.将右子树构造成双链表，并返回链表头节点。
5.如果右子树链表不为空的话，将该链表追加到root节点之后。
6.根据左子树链表是否为空确定返回的节点。
 * @param [type] $treeNode [description]
 */
function ConvertBSTToBiList1($treeNode)
{
	if ($treeNode == null) {
		return null;
	}
	if ($treeNode->left == null && ($treeNode->right == null)) {
		return $treeNode;
	}

	$leftNode = ConvertBSTToBiList1($treeNode->left);
	// 左孩子的最右孩子（左孩子中最大的）作为根节点的左孩子
	$curNode = $leftNode;
	while ($curNode!=null && ($curNode->right != null)) {
		$curNode = $curNode->right;
	}
	if ($leftNode != null) {
		$curNode->right = $treeNode;
		$treeNode->left = $curNode;
	}
    
	$rightNode = ConvertBSTToBiList1($treeNode->right);

	if ($rightNode != null) {
		$rightNode->left = $treeNode;
		$treeNode->right = $rightNode;
	}

    return $leftNode!=null? $leftNode : $treeNode;   

}




$treeNode = new TreeNode(10);
$treeNode->left= new TreeNode(6);
$treeNode->left->left = new TreeNode(4);
$treeNode->left->right = new TreeNode(8);
$treeNode->right = new TreeNode(14);
$treeNode->right->left = new TreeNode(12);
$treeNode->right->right = new TreeNode(16);

var_dump(ConvertBSTToBiList1($treeNode));